﻿// 0924train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <numeric>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <queue>

using namespace std;

/*
 一线运维人员在对通话流量进行监控，每一段时间内都是出现流量的高峰，
 流量有高有低形成一个个波峰波谷，运维人员想找到流量变化最快的波峰，你可以帮助他吗？

给定一个整数数组nums，代表采样点的流量值，请找到满足以下条件的三元组(i,j,k):
其中i<j<k，nums[i]<nums[j]且nums[j]>nums[k](即j是峰顶)，
并找到所有满足条件的三元组中(k-i)的最小值

输入描述
第一行为n个整数，表示数组中的n个元素，0<=n<=100000

输出描述
返回所有满足条件的三元组中(k-i)的最小值。若不存在，返回-1。

示例1:
输入：
3 5 4 7 2 1
输出：
2
说明：
满足条件的三元组为[0,1,2],距离2

示例2：
输入：
4 3 2 1
输出：
-1
说明：
无法找到满足条件的三元组，返回-1
 */
class Solution01
{
public:
    Solution01(vector<int>&num_vec)
    {
        vector<int>exec_queue;
        unordered_map<int, vector<int>>res_map;
        //左边第一个比当前小的，右边第一个比当前小的
        //nums[i]<nums[j]且nums[j]>nums[k]
        int v_size = num_vec.size();
        for (int i=0; i<v_size; i++)
        {
            int curr = num_vec[i];
            while (!exec_queue.empty() && num_vec[exec_queue.back()] >= curr)
            {
                exec_queue.pop_back();
            }
            if (!exec_queue.empty())
            {
                res_map[i].push_back(exec_queue.back());
            }
            //插入序号
            exec_queue.push_back(i);
            //for
        }
        exec_queue.clear();
        for (int i=v_size-1; i>=0; i--)
        {
            int curr = num_vec[i];
            while (!exec_queue.empty() && num_vec[exec_queue.back()] >= curr)
            {
                exec_queue.pop_back();
            }
            if (!exec_queue.empty())
            {
                res_map[i].push_back(exec_queue.back());
            }
            //插入序号
            exec_queue.push_back(i);
        }

        int min_length = INT_MAX;
        for (auto&map_item: res_map)
        {
            if (map_item.second.size() < 2) continue;
            int curr_len = map_item.second[1] - map_item.second[0];
            min_length = min(curr_len, min_length);
        }

        if (min_length==INT_MAX)
        {
            cout << -1;
            return;
        }
        cout << min_length;
	    //Solution01
    }
};


/*
 从一个长度为N的正数数组numbers中找出长度至少为L且几何平均值最大的子数组，
 并输出其位置和大小。（K个数的几何平均值为K个数的乘积的K次方根）  
若有多个子数组的几何平均值均为最大值，则输出长度最小的子数组
若有多个长度相同的子数组的几何平均值均为最大值，则输出最前面的子数组。  

输入描述：  
第一行输入为N、L，N表示numbers的大小(1<=N<=100000)，L表示子数组的最小长度(1<=L<=N)  
之后N行表示numbers中的N个数，每个一行(10^-9<=numbers<=10^9)。  

输出描述：  
输出子数组的位置(从0开始计数)和大小，中间用一个空格隔开。  

补充说明：  
用例保证几何平均值为最大值的子数组外，其他子数组的几何平均值至少比最大值小最大值的10^-10倍  

示例1：输入输出示例仅供调试，后台判题数据一般不包含示例  
输入  
3 2  
2  
2  
3  
输出：  
1 2  
说明：  
长度至少为2的子数组有3个，[2,2][2,3][2,2,3]，几何平均值最大为[2,3]，输出其位置1和长度2
 */
class Solution02
{
public:
    vector<int>checkVerify(double mid, vector<double>& num_vec, int L)
    {
        //前缀和
        int v_size = num_vec.size();
        double min_pre_sum = DBL_MAX;
        int min_pre_pos = -1;

        int curr_pos = -1, curr_len = v_size+1;
        vector<double>pre_sum(v_size + 1);
        pre_sum[0] = 1;
        //输出长度最小，最前面
        for (int i=1; i<L; i++)
        {
            pre_sum[i] = pre_sum[i - 1] * (num_vec[i - 1] / mid);
        }

        for (int i=L; i<=v_size; i++)
        {
            pre_sum[i] = pre_sum[i - 1] * (num_vec[i - 1] / mid);

            if (pre_sum[i-L]<min_pre_sum)
            {
                min_pre_sum = pre_sum[i - L];
                min_pre_pos = i - L;
            }
            if (pre_sum[i]>min_pre_sum && i - min_pre_pos < curr_len)
            {
                curr_pos = min_pre_pos;
                curr_len = i - min_pre_pos;
            }
        }

        if (curr_pos == -1) return {};
        //如果合格，返回起始位置和长度
        return { curr_pos, curr_len };

	    //checkVerify
    }

    Solution02(vector<double>&num_vec, int L)
    {
        //下界min(num_vec)上界max(num_vec)
        double left = *min_element(num_vec.begin(), num_vec.end());
        double right = *max_element(num_vec.begin(), num_vec.end());

        int curr_pos = 0, curr_len = L;

        while (right-left>pow(10,-10))
        {
            double mid = left + (right - left) / 2;
            vector<int>res = checkVerify(mid, num_vec, L);
            if (!res.empty())
            {
	            //满足条件
                curr_pos = res[0];
                curr_len = res[1];
                left = mid;
            }
            else
            {
                right = mid;
            }

            //while
        }

        cout << curr_pos << ' ' << curr_len;
        //Solution02
    }
};


/*
有一棵二叉树，每个节点由一个大写字母标识（最多26个节点）
两组字母，分别表示后序遍历（左孩子->右孩子->父节点）和中序遍历（左孩子->父节点->右孩子）的结果，
请输出层次遍历的结果。

输入描述
二叉树后序和中序遍历结果

输出描述
二叉树层序遍历结果

示例1
输入
CBEFDA CBAEDF
输出
ABDCEF
 */
class Solution03
{
public:
    struct TreeNode
    {
        char val;
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;
        TreeNode() = default;
        TreeNode(char val) :val(val) {};
        TreeNode(char val, TreeNode* left, TreeNode* right) :val(val), left(left), right(right) {};
    };
    void insertNode(TreeNode* root, TreeNode*node)
    {
        while (root!= node)
        {
            if (pos_map[node->val]<pos_map[root->val])
            {
                if (root->left==nullptr)
                {
                    root->left = node;
                }
                root = root->left;
            }
            else
            {
	            if (root->right==nullptr)
	            {
                    root->right = node;
	            }
                root = root->right;
            }
        }

    }

    Solution03(string&postorder_str, string&inorder_str)
    {
        int size = inorder_str.size();
        for (int i=0; i<size; i++)
        {
            char curr_ch = inorder_str[i];
            pos_map[curr_ch] = i;
        }

        //后序遍历最后一个节点，根节点
        TreeNode* root = new TreeNode(postorder_str[size - 1]);
        for (int i=size-2; i>=0; i--)
        {
            TreeNode* node = new TreeNode(postorder_str[i]);
            insertNode(root, node);
        }

        deque<TreeNode*>bfs_queue;
        bfs_queue.push_back(root);

        vector<char>res_vec;
        while (!bfs_queue.empty())
        {
            int q_size = bfs_queue.size();
            for (int i=0; i<q_size; i++)
            {
                TreeNode* top_node = bfs_queue.front();
                bfs_queue.pop_front();
                res_vec.push_back(top_node->val);

                if (top_node->left!=nullptr)
                {
                    bfs_queue.push_back(top_node->left);
                }
                if (top_node->right!=nullptr)
                {
                    bfs_queue.push_back(top_node->right);
                }

            }
        	//while---
        }

        for (auto&ch:res_vec)
        {
            cout << ch;
        }
	    //Solution03
    }
private:
    unordered_map<char, int>pos_map;
};


/*
 任务提交者和任务执行者都有编号，任务提交者在给定时刻向工作队列提交任务，任务有执行所需的时间。
 执行者取出任务的即刻加上执行时间即为任务完成的时刻。

 执行者完成任务变为空闲的时刻会从工作队列中取最老的任务执行，
 若这一时刻有多个空闲的执行者，其中优先级最高的会执行这个任务。

 编号小的执行者优先级高。初始状态下所有执行者都空闲。
 工作队列有最大长度限制，当工作队列满而有新的任务需要加入队列时，
 队列中最老的任务会被丢弃。

 特别的，在工作队列满的情况下，当执行者变为空闲的时刻和新的任务提交的时刻相同时，
 队列中最老的任务被取出执行，新的任务加入队列。

输入描述：
输入为两行。
第一行为2N个正整数，代表提交者提交的N个任务的时刻和执行时间。
第一个数字是第一个任务的提交时刻，第二个数字是第一个任务的执行时间，以此类推。
用例保证提交时刻不会重复，任务按提交时刻升序排列。
第二行为两个数字，分别为工作队列的最大长度和执行者的数量。两行的数字都由空格分隔。
N不超过20，数字为不超过1000的正整数。

输出描述：
输出两个数字，分别为最后一个任务执行完成的时刻和被丢弃的任务的数量，数字由空格分隔。

示例1：
输入：
1 3 2 2 3 3
3 2
输出：
7 0

示例2：
输入：
1 6 2 4 4 3 6 3
1 2
输出：
10 0

示例3：
输入：
1 6 2 4 3 3 4 3 6 3
1 2
输出：
10 1

第一个数字是第一个任务的提交时刻，第二个数字是第一个任务的执行时间
工作队列的最大长度和执行者的数量
 */
class Solution04
{
public:
    Solution04(vector<vector<int>>&task_vec, int queue_len, int exec_len)
    {
/*
1 3 2 2 3 3
3 2
*/
        int start_time = task_vec[0][0];
        int curr_time = start_time;
        int lose_count = 0;
        //第一个任务入列
        deque<vector<int>>wait_queue;
        deque<vector<int>>exec_queue;
        exec_queue.push_back(task_vec[0]);

        //待入队任务
        int task_size = task_vec.size();
    	int index = 1;
        while (!wait_queue.empty() || !exec_queue.empty())
        {
            curr_time++;

            deque<vector<int>>new_exec_queue;
            for (auto& item : exec_queue)
            {
                item[1] -= 1;
                if (item[1] > 0)
                {
                    new_exec_queue.push_back(item);
                }
            }
            exec_queue = new_exec_queue;

            int need_count = 0;
            int exec_queue_size = exec_queue.size();
            if (exec_queue_size < exec_len)
            {
                need_count = exec_len - exec_queue_size;

                int real_q_size = wait_queue.size();
                int q_size = min(real_q_size, need_count);
                for (int i = 0; i < q_size; i++)
                {
                    vector<int>top_node = wait_queue.front();
                    wait_queue.pop_front();
                    exec_queue.push_back(top_node);
                }
            }


            //加入的逻辑
            if (index < task_size && task_vec[index][0] == curr_time)
            {
                int exec_queue_size = exec_queue.size();
                if (wait_queue.empty() && exec_queue_size<exec_len)
                {
                    exec_queue.push_back(task_vec[index]);
                }
                else
                {
                    wait_queue.push_back(task_vec[index]);
                    int q_size = wait_queue.size();
                    if (q_size > queue_len)
                    {
                        wait_queue.pop_front();
                        lose_count++;
                    }
                }
                
                index++;
            }
            
            //while---
        }
        cout << curr_time << ' ' << lose_count;
	    //Solution04
    }
};


class Solution14
{
public:
    Solution14(vector<vector<int>>& task_vec, int queue_len, int exec_len)
    {
        vector<int>exector_v(exec_len);
        deque<int>wait_queue;

        int index = 0, final_time = 0, reject_count = 0;
        int task_size = task_vec.size();
        while (index<task_size || !wait_queue.empty())
        {
            //next_time要么等于下一个到达，要么等于最先结束
            int next_time = INT_MAX;
            if (index < task_size) next_time = task_vec[index][0];
            for (auto&busy_time:exector_v)
            {
                if (busy_time == 0)continue;
                next_time = min(next_time, busy_time);
            }
            if (next_time == INT_MAX) break;

            //寻找空的执行器
            deque<int>free_v;
            for (int i=0; i<exec_len; i++)
            {
                if (exector_v[i]<=next_time)
                {
                    free_v.push_back(i);
                    exector_v[i] = 0;
                }
                
            }

            //从工作队列里抽出任务
            int count = min(free_v.size(), wait_queue.size());
            for (int i=0; i<count; i++)
            {
                int top_i = wait_queue.front();
                wait_queue.pop_front();
                int cost_time = task_vec[top_i][1];
                int free_i = free_v.front();
                exector_v[free_i] = next_time + cost_time;
                free_v.pop_front();
            }
            

            //加入任务
            while (index<task_size&& task_vec[index][0]<=next_time)
            {
                if (!free_v.empty())
                {
                    //如果有空闲执行器，优先进执行器
                    int free_i = free_v.front();
                    free_v.pop_front();
                    int cost_time = task_vec[index][1];
                    exector_v[free_i] = next_time + cost_time;
                    index++;
                    continue;
                }


                if (wait_queue.size()==queue_len)
                {
                    wait_queue.pop_front();
                    reject_count++;
                }
                wait_queue.push_back(index);
                index++;
				//while
            }

            //扫一遍，更新最终结束时间
            for (auto&busy_time:exector_v)
            {
                final_time = max(busy_time, final_time);
            }
	        //while
        }

        cout << final_time << ' ' << reject_count;
	    //Solution14
    }
};


/*
 实现一个支持优先级的队列，高优先级先出队列，同优先级时先进先出。
如果两个输入数据和优先级都相同，则后一个数据不入队列被丢弃。
队列存储的数据内容是一个整数

输入描述
一组待存入队列的数据（包含内容和优先级）。
输出描述
队列的数据内容（级优先信息输出时不再体现）。
补充说明
不用考虑数据不合法的情况，测试数据不超过100个

示例1
输入：
(10,1),(20,1),(30,2),(40,3)
输出：
40,30,10,20
说明：
输入样例中，向队列写入了4个数据，每个数据由数据内容和优先级组成。
输入和输出内容都不含空格。数据40的优先级最高，所以最先输出，其次是30;10和20优先级相同，
所以按输入顺序输出

示例2
输入：
(10,1),(10,1),(30,2),(40,3)
输出：
40,30,10
说明：
输入样例中，向队列写入了4个数据，每个数据由数据内容和优先级组成输入和输出内容都不含空格。
数据40的优先级最高，所以最先输出，其次是30;两个10和10构成重复数据，被丢弃一个。
 */
class Solution05
{
public:
    struct Node
    {
        int val, weight, index;
        Node() = default;
        Node(int val, int weight,int index) :val(val), weight(weight),index(index){};
        bool operator<(const Node&other)const
        {
            if (weight==other.weight)
            {
                return index > other.index;
            }

            return weight < other.weight;
        }
    };
    Solution05(string&num_str)
    {
	    //(10,1),(20,1),(30,2),(40,3)
        priority_queue<Node>p_queue;
        //两个输入数据和优先级都相同，则后一个数据不入队列被丢弃
        unordered_set<string>str_set;
        bool is_left = false;
        bool is_right = false;
        int val = 0, weight = 0;
        int num_str_size = num_str.size();
        for (int i=0;i<num_str_size;i++)
        {
            char curr_ch = num_str[i];
            if (curr_ch=='(')
            {
                is_left = true;
            }
            else if (curr_ch==')')
            {
                is_right = false;
                stringstream oh_sstream;
                oh_sstream << val << ',' << weight;
                string curr_str = oh_sstream.str();
                if (str_set.count(curr_str)==0)
                {
                    p_queue.push(Node(val, weight, i));
                }
                str_set.insert(curr_str);
                val = 0;
                weight = 0;
            }
            else if (curr_ch==',')
            {
                if (is_left)
                {
                    is_left = false;
                    is_right = true;
                }
            }
            else
            {
                if (is_left) val = val * 10 + curr_ch - '0';
                if (is_right) weight = weight * 10 + curr_ch - '0';
            }

        }

        string result;
        while (!p_queue.empty())
        {
            Node top_node = p_queue.top();
            p_queue.pop();

            result += to_string(top_node.val);
            result += ',';
            //while
        }
        int size = result.size();
        result = result.substr(0, size - 1);
        cout << result;

        //Solution05
    }
};


int main()
{
	{
        //(10,1),(10,1),(30,2),(40,3)
        string input;
        cin >> input;
        Solution05 solu(input);

        return 0;
	}
	{
        //1 3 2 2 3 3
        //3 2
        vector<vector<int>>task_vec;
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        vector<int>item_v;
        while (oh_sstream>>token)
        {
            item_v.push_back(stoi(token));
            if (item_v.size()==2)
            {
                task_vec.push_back(item_v);
                item_v.clear();
            }
        }
        string input_2;
        getline(cin, input_2);
        vector<int>base_v;
        stringstream base_sstream(input_2);
        while (base_sstream>>token)
        {
            base_v.push_back(stoi(token));
        }

        Solution14 solu(task_vec, base_v[0], base_v[1]);

        return 0;
	}
	{
        string postorder_str, inorder_str;
        cin >> postorder_str >> inorder_str;

        Solution03 solu(postorder_str, inorder_str);

        return 0;
	}
	{
        int v_size, L;
        cin >> v_size >> L;

        vector<double>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        Solution02 solu(num_vec, L);

        return 0;
	}
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    vector<int>num_vec;
    while (oh_sstream>>token)
    {
        num_vec.push_back(stoi(token));
    }
    Solution01 solu(num_vec);


}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
